#! /usr/bin/python

import string, random


class City:
    ''' Class instances represent cities '''

    listofCities = []

    def __init__(self,name,neighbors=None): #beware, not neighbors=[]
	self.name = name
	if neighbors is None:
	    self.neighbors = []
	else:
	    self.neighbors = neighbors
	City.listofCities.append(self)

#    def __str__(self):
#	s = []
#	if not self.neighbors:
#	    for n in self.neighbors:
#		s += [n.name]
#	return str(self.name) + ':' + ' '.join(s)

    def findpath(self,destination,path=None):
	''' Finds path from self to destination '''
	print self.name
	if self is destination:
	    return path+[self]
	else:
	    if not path: path = [self]
	    else: path.append(self)
	    #print [n.name for n in path]
	    #print [n.name for n in path]
	    #if destination in self.neighbors: return path+[destination]
	    #else:
	    for neighbor in self.neighbors:
		print '\t',[n.name for n in path],neighbor.name
		if neighbor is destination:
		    return path + [neighbor]
		elif neighbor not in path:
		    path = neighbor.findpath(destination,path)
		else:
		    pass
		    #continue

	path.remove(self)
	return path

n=6
nodeList = []
nameList = []
for i in range(n):
    name = random.choice(string.uppercase)
    while name in nameList:
	name = random.choice(string.uppercase)
    nameList += [name]
    nodeList.append(City(name))

#print [n.name for n in nodeList]
for node in nodeList:
    rand = random.randint(2,3)
    #rand = 1
    #randNode = node
    neighbList = [node]
    for i in range(rand):
	randNode = random.choice(nodeList)
	while randNode in neighbList:
	    randNode = random.choice(nodeList)
	#print node.name,randNode.name, [n.name for n in node.neighbors]
	node.neighbors.append(randNode)
	#print node.name , [n.name for n in node.neighbors]
	neighbList.append(randNode)

for node in nodeList:
    #print node.name,':',' '.join(map(str,node.neighbors))
    print node.name, [x.name for x in node.neighbors]
    #print node.name,node.neighbors
    #print ' '.join(map(str,[city.name for city in City.listofCities]))
    pass
print "THE PATH TO FREEDOM IS: ",nodeList[0].name,nodeList[1].name
path = nodeList[0].findpath(nodeList[1])
if path:
    print [n.name for n in path]
else:
    print "NO WAY!"
print "\n***************NODES**************************"
